﻿#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"sort.h"
#include"Stack.h"

void Swap(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t;
}
//直接插入排序
void InsertSort(int* arr, int n)
{
	//每次插入一个数据
	for (int i=0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		//插入正确位置
		while (end >= 0&&arr[end]>tmp)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = tmp;
	}
}

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i <n-gap ; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0 && arr[end] > tmp)
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = tmp;
		}
	}
}

//直接选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	int maxi, mini;
	while (begin < end)
	{
		maxi = mini = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] > arr[maxi])
				maxi = i;
			if (arr[i] < arr[mini])
				mini = i;
		}
		Swap(&arr[begin], &arr[mini]);
		if (maxi == begin)
			maxi = mini;
		Swap(&arr[end], &arr[maxi]);
		begin++;
		end--;
	}
}

//堆排序
void HeapSort(int* arr, int n)
{
	//向下调整建堆
	//遍历父结点
	for (int tmp = (n-1-1) / 2; tmp >= 0; tmp--)
	{
		int child = tmp  * 2+1;
		int parent = tmp;
		while(child<n)
		{
			if (child + 1 < n && arr[child] < arr[child + 1])
				child++;
			if (arr[child] > arr[parent])
			{
				Swap(&arr[child], &arr[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}

	//删除堆顶数据
	for (int i = n - 1; i >=0; i--)
	{
		Swap(&arr[0], &arr[i]);
		//向下调整使堆顶为最大值
		int parent = 0;
		int child = parent*2+1;
		//交换后堆有效数据的最后一个元素
		int end = i - 1;
		while (child <=end)
		{
			if (child + 1 <=end && arr[child] < arr[child + 1])
				child++;
			if (arr[parent] < arr[child])
			{
				Swap(&arr[child], &arr[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}
		
}

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i-1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
			}
		}
	}
}

// 三数取中
int median_of_three(int arr[], int left, int right) {
	int mid = left + (right - left) / 2;

	if ((arr[left] <= arr[mid] && arr[mid] <= arr[right]) || (arr[right] <= arr[mid] && arr[mid] <= arr[left])) {
		return mid;
	}
	else if ((arr[mid] <= arr[left] && arr[left] <= arr[right]) || (arr[right] <= arr[left] && arr[left] <= arr[mid])) {
		return left;
	}
	else {
		return right;
	}

}
//hoare分区
int _QuickSort(int* arr, int left, int right)
{
	int keyi = left;
	/*left++;*/
	//left和right相遇循环结束
	while (left < right)
	{
		//right先走保证最终right的比keyi位置小或right为keyi
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		
		if(left<right)
		Swap(&arr[left++], &arr[right--]);
	}
	//right和left相等
	/*if (arr[right] > arr[keyi])
		right--;*/
	Swap(&arr[right], &arr[keyi]);
	return right;
}

//lomuto前后指针法
int _lmtQuickSort(int* arr, int left, int right)
{
	int key = arr[right];
	int prev, cur;
	prev = left - 1;
	for (cur = left; cur < right; cur++)
	{
		//arr[cur] <= key不满足会短路，跳过++prev!=cur
		if (arr[cur] <= key && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
	}
	Swap(&arr[right], &arr[prev+1]);
	return prev+1;
}

//快速排序-自省排序
void introSort(int* arr, int left, int right,int depth,int depth_limit)
{
	if (left >= right)
	{
		return;
	}
	//数组长度小于16的数组改为插入排序，简单递归次数
	if (right - left + 1 < 16)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}
	if (depth >= depth_limit)
	{
		HeapSort(arr + left, right - left + 1);
		return;
	}
	depth++;

	int key = arr[right];
	int prev, cur;
	prev = left - 1;
	for (cur = left; cur < right; cur++)
	{
		//arr[cur] <= key不满足会短路，跳过++prev!=cur
		if (arr[cur] <= key && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
	}
	Swap(&arr[right], &arr[prev + 1]);
	
	introSort(arr, left, prev, depth, depth_limit);
	introSort(arr, prev+2, right, depth, depth_limit);
}

//三路划分法
void three_way_partition(int*arr,int left,int right)
{
	if (left >= right)
		return;
	int key = arr[right];
	int begin = left,cur=left;
	left--;
	int end = right;
	while (cur < right)
	{
		if (arr[cur] < key)
		{
			Swap(&arr[++left], &arr[cur++]);
		}
		else if (arr[cur] > key)
		{
			//交换后cur不能++因为换过来的数据不知道与key的关系不能跳过
			Swap(&arr[--right], &arr[cur]);
		}
		//等于key跳过cur直接++
		else if(arr[cur]==key)
			cur++;
	}
	Swap(&arr[right], &arr[end]);
	//将原数组划分为【begin,left】【left+1,right】【right+1,end】
	three_way_partition(arr, begin, left);
	three_way_partition(arr, right+1, end);

}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	//生成基准值并分区
	//三数取中法找基准值
	//int mid=median_of_three(arr, left, right);
	//Swap(&arr[mid], &arr[left]);
	int keyi = _QuickSort(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);

}

//非递归版本快速排序
void QuickSortNOR(int* arr, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, left);
	STPush(&st, right);
	while (!STEmpty(&st))
	{
		int end = STTop(&st);
		STPop(&st);
		int begin = STTop(&st);
		STPop(&st);
		int key = arr[end];
		int prev, cur;
		prev = cur = begin;
		while (cur < end)
		{
			if (arr[cur] <= key)
			{
				Swap(&arr[cur], &arr[prev]);
				prev++;
			}
			cur++;
		}
		//将基准值交换到prev位置
		Swap(&arr[prev], &arr[end]);
		if (prev - 1 > begin)
		{
			STPush(&st, begin);
			STPush(&st, prev - 1);
		}
		if (end > prev + 1)
		{
			STPush(&st, prev + 1);
			STPush(&st, end);
		}
	}

	STDestroy(&st);
}

//归并排序
void MergeSort(int* arr, int left,int right,int *tmp)
{
	if (right <= left)
		return;
	int mid;
	mid = (left + right) / 2;
	//将原数组划分为[left,mid]和[mid+1，right]两个数组
	MergeSort(arr, left, mid,tmp);
	MergeSort(arr, mid+1, right,tmp);
	//合并两个数组
	int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right,i=0;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i] = arr[begin1];
			begin1++;
		}
		else {
			tmp[i]=arr[begin2];
			begin2++;
		}
		i++;
	}
	//插入剩余元素
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//将两个子序列并的有序数组导入原数组对应位置中
	i = 0;
	while (left <= right)
	{
		arr[left++]=tmp[i++];
	}
}

void mergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

//非递归-归并排序
void nonreMergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	//gap是每层每个待合并子序列的元素个数
	int gap = 1;
	//所有层
	for (gap; gap < n; gap *= 2)
	{
		//每层
		for (int i = 0;i<n;i+=2*gap)
		{
			//合并两个序列
			int begin1, begin2, end1, end2,index;
			begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1;
			index = 0;

			//处理end1、begin2、end2越界情况
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			if (begin2 >= n)
			{
				//begin2>=n就没有第二个序列了本层结束
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[index++] = arr[begin1++];
				else
					tmp[index++] = arr[begin2++];
			}
			while (begin1 <= end1)
			{
				tmp[index++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = arr[begin2++];
			}
			//复制到原数组对应位置
			begin1 = i;
			for (int j = 0; j < index; j++)
			{
				arr[begin1++] = tmp[j];
			}
		}
	}
	free(tmp);
	tmp = NULL;
}

//计数排序
void CountSort(int* arr, int n)
{
	int max, min;
	max = min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] < min)
			min = arr[i];
		if (arr[i] > max)
			max = arr[i];
	}
	int size = max - min + 1;
	int* count = (int*)calloc(size,sizeof(int));
	if (count == NULL)
	{
		exit(1);
	}
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	//index作为arr数组的索引
	int index = 0;
	for (int i = 0; i < size; i++)
	{
		//元素出现次数
		while (count[i]--)  //count[i]是在循环条件判断完--
		{
			arr[index++] = i + min;
		}
	}
	free(count);
	count = NULL;
}